Selepas menjalankan tugasnya sebagai anggota tentera di Sudan beliau telah dilantik sebagai seorang pensyarah di Akademi Tentera Di-Raja Mesir pada 1942. Beliau telah menggunakan kedudukannya untuk menubuhkan satu kumpulan yang dikenali sebagai Pegawai Bebas (Free Officers) satu gerakan nasionalis Mesir dan di antara ahlinya termasuklah Anwar Sadat, Abd-al Hakim Amer dan Zakaria Mohiedin.

Pada 1949 beliau bersama ahli kumpulannya telah turut serta dalam Perang Arab-Israel di Palestin. Di sana kumpulannya telah terperangkap dalam kawasan yang dikenali sebagai "Poket Faluja" dan beliau nyaris maut akibat kecederaan di dadanya. Peperangan ini telah meningkatkan kebencian mereka terhadap golongan monarki kerana ketidakcekapan mereka serta kehidupan mereka yang mewah. Apabila perdamaian tercapai, Gamal Abdel Nasser dibenarkan kembali ke Mesir. Pada tahun 1952, Gamal Abdel Nasser mengetuai rampasan kuasa ketenteraan dan berjaya menggulingkan raja pada ketika itu iaitu Raja Farouk I.

Selepas Raja Farouk I digulingkan, Nasser telah menaikkan Major Jeneral Muhammad Naguib sebagai Presiden dan Perdana Menteri Mesir yang pertama, manakala beliau pula menjadi timbalan perdana menteri dan menteri dalam negeri. Mohamed Naquib merupakan seorang wira perang dunia II dan disegani oleh rakyat jelata. Namun demikian, ahli kumpulannya mula bimbang dengan Naguib yang sangat konservatif dan terlampau autoritarian. Oleh itu pada awal 1954, atas alasan berpakat dengan parti ekstremis Ikhwanul Muslimun, Presiden Naguib telah disingkirkan jawatan dan ditahan. Pada 25 Februari 1954 Gamal Abdel Nasser menjadi Yang Terutama Mesir. Dua tahun kemudian, beliau menjadi calon tunggal dalam pilihan raya presiden dan dilantik menjadi presiden Mesir kedua.